package com.zpself.module.算法练习.算法.动态规划;

/**
 * 动态规划：先求出前面小的最优结果，大的结果根据小的来获得最优解
 * @author By ZengPeng
 * @Description 0-1背包问题
 * 有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
 * eg：number＝4，capacity＝8
 *
 * @date in  2021/1/20 19:13
 * @Modified By
 */
public class 动态规划0_1背包 {
    public static void main(String[] args) {
        int[] w = {2, 1, 3, 2};
        int[] v = {12, 10, 20, 15};
        System.out.println(knapSack(w, v, 5));
    }

    /**
    *  实现 int[][]
     *  w(i)>c     f(w,c)= f(w-1,c)
     *  w(i)<=c    f(w,c)= f(w-1,c - v[i])+v[i]    与   f(w-1,c)   的最大值
    * @param  w 物品重量
    * @param  v 物品价值
    * @param  C 背包容量
    **/
    public  static  int knapSack(int[] w, int[] v, int C){
        int size = w.length;
        if(size==0)
            return 0;

        int[][] dp = new int[size+1][C+1];
        //初始化第一列 第一行：当容量为0时 价值为0
        //补充其它行和列
        for (int i = 1 ; i <= C; i++) {//容量为i时，i为第几列
            for (int j = 1; j <= w.length; j++) {//j为有多少物品，j为第几行
                if(w[j-1]>i)//当第j个物品的质量大于i ,
                    dp[j][i]  = dp[j][i-1];
                else
                    dp[j][i] = Math.max(dp[j][i-1],dp[j-1][i-w[j-1]]+v[j-1]);
            }
        }
        for (int i = 0; i < dp.length; i++) {
            int[] ints = dp[i];
            for (int j = 0; j < ints.length; j++) {
                int anInt = ints[j];
                System.out.print(anInt+",");
            }
            System.out.println();
        }
        return dp[size][C];
    }
}
